﻿using System;
using System.Collections.Generic;
using System.Linq;

using RobozzleModel;

/// <summary>
/// Summary description for SolutionVerifier
/// </summary>
public class SolutionVerifier
{
    private class RobozzleStackEntry
    {
        public int Function { get; set; }
        public int Instruction { get; set; }
    }

    public bool IsSolution(Level levelInfo, string program)
    {
        return IsSolution(levelInfo, ParseSolution(program));
    }

    /// <summary>
    /// Check to see if the program solves the level.
    /// </summary>
    /// <param name="levelInfo">Information about the level.
    /// This function assumes that the levelInfo is a valid level.</param>
    /// <param name="commands">The program to run.
    /// The program is an array of functions.
    /// A function is an array of commands.
    /// A command can be for example: "_F", "rL", "_r" or "g2".
    /// This function assumes that the program is a valid program for the level.
    /// </param>
    /// <returns>True iff the program is a solution to the level.</returns>
    public bool IsSolution(Level levelInfo, string[][] commands)
    {
        // Check assumption required for this code to work.
        if (RobozzleService.MAX_SUBS > 9)
            throw new InvalidOperationException("There cannot be more than 9 functions.");

        // Initialize the state before running the program.
        int commandsExecuted = 0;
        int fp = 0; // Current function pointer.
        int ip = 0; // Current instruction pointer.
        Stack<RobozzleStackEntry> stack = new Stack<RobozzleStackEntry>();
        bool[,] starsHit = new bool[RobozzleService.ROWS, RobozzleService.COLS];
        int row = levelInfo.RobotRow;
        int column = levelInfo.RobotCol;
        int direction = levelInfo.RobotDir;
        string[] colorsString, items;
        RobozzleService.EntityToObj(levelInfo.Board, out colorsString, out items);
        char[][] colors = colorsString.Select(x => x.ToCharArray()).ToArray();
        int starsRemaining = items.Select(x => x.ToCharArray()
                                                .Count(c => c == RobozzleService.ITEM_STAR))
                                  .Sum();
        bool[] functionMask = new bool[commands.Length]; // Loop detection mask.

        long steps = 0;

        // Run the program.
        while (commandsExecuted < RobozzleService.MAX_COMMANDS)
        {
            steps++;
            // If we have reached the end of the function, return.
            if (ip == commands[fp].Length)
            {
                if (stack.Count == 0)
                    return false; // Program terminated.

                functionMask[fp] = false;
                RobozzleStackEntry stackEntry = stack.Pop();
                fp = stackEntry.Function;
                ip = stackEntry.Instruction;
                continue;
            }

            // Process the command.
            string command = commands[fp][ip];

            // Check the condition on the command.
            char condition = command[0];
            if (condition != RobozzleService.COLOR_NONE && condition != colors[row][column])
            {
                // Condition not satisfied. Skip this command.
                ++ip;
                continue;
            }

            // Execute the command.
            char commandType = command[1];
            if (commandType >= '1' && commandType <= '0' + RobozzleService.MAX_SUBS)
            {
                int nextFunction = commandType - '1';

                // Detect an infinite loop.
                if (functionMask[nextFunction])
                    return false;
                functionMask[nextFunction] = true;

                // Push the return address.
                stack.Push(new RobozzleStackEntry { Function = fp, Instruction = ip + 1 });

                // Jump to the beginning of the next function.
                fp = nextFunction;
                ip = 0;
            }
            else
            {
                switch (commandType)
                {
                    case 'F':
                        // Move forward.
                        switch (direction)
                        {
                            case RobozzleService.DIRECTION_RIGHT: column++; break;
                            case RobozzleService.DIRECTION_DOWN: row++; break;
                            case RobozzleService.DIRECTION_LEFT: column--; break;
                            case RobozzleService.DIRECTION_UP: row--; break;
                        }

                        // Check if the robot fell off the board.
                        if (row < 0 || row >= RobozzleService.ROWS) return false;
                        if (column < 0 || column >= RobozzleService.COLS) return false;
                        char item = items[row][column];
                        if (item == RobozzleService.ITEM_HOLE) return false;

                        // Check if we hit a star we haven't hit before.
                        if (item == RobozzleService.ITEM_STAR && !starsHit[row, column])
                        {
                            starsHit[row, column] = true;
                            starsRemaining--;
                            if (starsRemaining == 0)
                                return true;
                        }

                        break;

                    case 'R': direction = (direction + 1) % 4; break;
                    case 'L': direction = (direction + 3) % 4; break;
                    case 'r': colors[row][column] = RobozzleService.COLOR_RED; break;
                    case 'g': colors[row][column] = RobozzleService.COLOR_GREEN; break;
                    case 'b': colors[row][column] = RobozzleService.COLOR_BLUE; break;
                    default:
                        throw new InvalidOperationException("Unknown Robozzle command.");
                }

                commandsExecuted++;
                functionMask = new bool[commands.Length];

                // Advance the instruction pointer.
                ++ip;
            }
        }

        return false;
    }

    private static string[][] ParseSolution(string solution)
    {
        // Split the solution into functions.
        string[] functions = solution.Split('|').Take(RobozzleService.MAX_SUBS).ToArray();

        // Split the functions into individual commands.
        // Convert the color conditionals to upper case.
        string[][] commands = new string[functions.Length][];
        for (int i = 0; i < commands.Length; ++i)
        {
            string f = functions[i];
            commands[i] = new string[f.Length / 2];
            for (int j = 0; j < f.Length / 2; j++)
                commands[i][j] = f[j * 2].ToString().ToUpper() + f[j * 2 + 1];

        }
        return commands;
    }
}
